Math 512: Finite Model Theory Complexity background

John Baldwin

February 5, 1997

References: Ebbinghaus and Flum, Chapter 6 Lewis and Papadimitrou Papadimitrou, Computational Complexity Neil Immerman, Descriptive Complexity: A logician’s approach to computation, No-

tices AMS, October 1995, 1127-1133.

0.1 Definition. 1. A configuration of a Turing machine is a triple ⟨s, w, u⟩ where s is the current state, w is a string terminating in the position of the cursor and u is the string of the remaining non-blank cells on the tape.

2. ⟨s, w, u⟩ immediately yields ⟨s′, w′, u′⟩ under M if the second configuration is the result of applying M to the first configuration. We write ⟨s, w, u⟩ →^{M} ⟨s′, w′, u′⟩.

3. ⟨s, w, u⟩ yields ⟨s′, w′, u′⟩ under M, written ⟨s, w, u⟩ →^{M}^{∗} ⟨s′, w′, u′⟩ is the transitive

closure of this relation.

4. ⟨s, w, u⟩ yields in p steps ⟨s′, w′, u′⟩ under M, written ⟨s, w, u⟩ →^{M}^{p} ⟨s′, w′, u′⟩, if

⟨s′, w′, u′⟩ results from ⟨s, w, u⟩ by p steps in the machine computation. For convenience, we assume all Turing machines begin reading the symbol I. A

multitape machine contains one read-only tape containing the input. For space bounds we consider only the space used on the work tapes. Either the max of the space on the work tapes or the sum can be used. The notation of the previous definition can be suitably complicated to describe multiple tapes.

Note that the length of the code for a structure A is |A|^{r} for r depending on the language not just |A| for either the Vaananen coding or the E and F coding.

0.2 Definition. 1. The language L is decided by machine M in time f(n) if for every input string w, ⟨S, I, w⟩ →^{M}^{f(|w|} ⟨Q, ∗, ∗⟩ where Q is either an accepting state if w ∈ L or a rejecting state if w ∉ L and * can be anything.

2. L is decided in time f(n) if some multitape Turing machine does so.

0.3 Remark. Decides is taken in the strongest possible way; see ‘strongly witnesses’ (E and F page 147.)

0.4 Fact. (Papadimitrou page 30) For any k-string Turing machine M, operating in time f(n) there is 1-tape machine which accepts the same strings in time f(n^{2}).

0.5 Fact. (Papadimitrou page 147) space(f(n)) ⊆ nspace(f(n)) ⊆ time(k^{log n+f(n)} (where k is the number of tapes).

0.6 Theorem. For any first order sentence ϕ, the collection of finite models of ϕ is decidable

1. POLYNOMIAL TIME

2. LOGSPACE

Proof. Since LOGSPACE implies POLYNOMIAL TIME it suffices to prove the second assertion. Show by induction on k that for a formula θ(\overline{x}) with k quantifiers, for any structure and any \overline{a} ∈ A, A ⊧ θϕ(\overline{a}) is decidable in LOGSPACE.

0.7 Theorem. Σ_{1}^{1} = NP.

Proof. The easy direction is Σ_{1}^{1} ⊆ NP. Suppose K is the class of L reducts of the L^{+}- sentence ϕ. Nondeterministically, let the machine write a code for a possible expansion of the L-structure A to an L^{+}-structure A^{+}. Check (in logspace) whether A^{+} ⊧ ϕ. For the converse, we copy the proof of Traktenbrot’s theorem, with one key difference. We want to design a sentence ϕ which is satisfied by a model A just if A encodes a computation of a Turing machine M on input w. The key difference is that time and tape are indexed by |w|^{k} where we know the time bound is n^{k}.